#include <iostream>
#include <cstdio>
#include <algorithm>
struct Set;
struct setNode{
int value;
setNode* next=nullptr;
Set* mS=nullptr;
setNode(int _value, Set* _mS): value(_value), mS(_mS) {}
};
struct Set{
setNode *head=nullptr, *tail=nullptr;
int sN;
Set(int _sN): sN(_sN){}
~Set(){}
void Insert(int value){
setNode* nN=new setNode(value, this);
if(head==nullptr) {
head=nN;
tail=nN;
}
else {
setNode* cur=this->head;
while(cur->next!=nullptr) cur=cur->next;
cur->next=nN;
}
}
void Delete(int value){
if(head==nullptr){
perror("NO KEY VALUE");
exit(1);
}
setNode* cur=this->head;
while(cur->next!=nullptr && cur->next->value!=value){
cur=cur->next;
}
if(cur->next!=nullptr){
setNode* tmp=cur->next->next;
cur->next=tmp;
delete cur->next;
}
}
};
struct Sets{
static int sN;
Set** sets;
int maxSz=4, cap=0;
Sets(){
sets=new Set*[maxSz];
}
void MakeSet(int x){
if(this->maxSz==this->cap){
Set** newSets=new Set*[this->maxSz*2];
for(int i=0; i<this->cap; ++i) newSets[i]=sets[i];
delete[] sets;
sets=newSets;
maxSz*=2;
}
Set* nS=new Set(sN++);
nS->Insert(x);
sets[cap++]=nS;
}
Set* FindSet(int x){
for(int i=0; i<cap; ++i){
Set* curS=sets[i];
setNode* curN=curS->head;
if(curN==nullptr) continue;
while(curN!=nullptr){
if(curN->value==x) return curS;
curN=curN->next;
}
}
return nullptr;
}
void Union(int x, int y){
Set* setX=FindSet(x);
Set* setY=FindSet(y);
if(setX==nullptr || setY==nullptr){
perror("NO KEY VALUE");
exit(1);
}
if(setX==setY) return;
for(int i=0; i<this->cap; ++i){
if(this->sets[i]==setY){
sets[i]=sets[cap-1];
sets[cap-1]=nullptr;
break;
}
}
setNode* cur=setY->head;
do{
cur->mS=setX;
cur=cur->next;
}while(cur!=nullptr);
setX->tail->next=setY->head;
setX->tail=setY->tail;
cap--;
delete setY;
}
};
int Sets::sN=1;
struct graphNode{
int value;
graphNode* next=nullptr;
graphNode(int _value): value(_value) {}
};
struct adjList{
graphNode** aL;
int vN, eN;
adjList(int _vN, int E[][2], int _eN): vN(_vN), eN(_eN){
aL=new graphNode*[this->vN];
for(int i=0; i<this->eN; ++i){
graphNode* nN1=new graphNode(E[i][1]);
graphNode* nN2=new graphNode(E[i][0]);
if(aL[E[i][0]-1]==nullptr){
aL[E[i][0]-1]=nN1;
} else {
graphNode* tmp=aL[E[i][0]-1];
aL[E[i][0]-1]=nN1;
nN1->next=tmp;
}
if(aL[E[i][1]-1]==nullptr){
aL[E[i][1]-1]=nN2;
} else {
graphNode* tmp=aL[E[i][1]-1];
aL[E[i][1]-1]=nN2;
nN2->next=tmp;
}
}
}
};
struct Index{
int value=-1;
int index=-1;
Index(){}
};
bool compare(Index A, Index B){
return A.value<B.value;
}
struct IndexSort{
Index* iSort;
int* index;
int sz;
IndexSort(int* value, int _sz): sz(_sz){
iSort=new Index[this->sz];
index=new int[this->sz];
for(int i=0; i<this->sz; ++i){
iSort[i].value=value[i];
iSort[i].index=i;
}
}
~IndexSort(){
delete iSort;
delete index;
}
int* returnIndex(void){
std::sort(iSort, iSort+this->sz, compare);
for(int i=0; i<this->sz; ++i) this->index[i]=iSort[i].index;
return this->index;
}
};
struct retList{
int* data;
int cap=0, sz;
retList(int _sz): sz(_sz) {
this->data=new int[this->sz];
}
~retList(){
delete data;
}
void Insert(int val){
if(this->cap==this->sz){
perror("OVERFLOW");
exit(1);
}
data[cap++]=val;
}
void print(void){
for(int i=0; i<this->cap; ++i){
std::cout<<this->data[i]<<' ';
}
std::cout<<std::endl;
}
};
retList* MST_Kruskal(adjList* graph, int* w, int E[][2]){
Sets* sets=new Sets();
retList* A=new retList(graph->eN);
for(int v=0; v<graph->vN; ++v){
sets->MakeSet(v+1);
}
IndexSort* iSort=new IndexSort(w, graph->eN);
int* index=iSort->returnIndex();
for(int i=0; i<graph->eN; ++i){
int edgN=index[i];
int u=E[edgN][0], v=E[edgN][1];
if(sets->FindSet(u)!=sets->FindSet(v)){
A->Insert(edgN);
sets->Union(u, v);
}
}
return A;
}
int main(void){
int E[14][2]={
{1, 2}, {1, 8}, {2, 3}, {2, 8}, {3, 4}, {3, 6}, {3, 9},
{4, 5}, {4, 6}, {5, 6}, {6, 7}, {7, 8}, {7, 9}, {8, 9}
};
int weight[14]={4, 8, 8, 11, 7, 4, 2, 9, 14, 10, 2, 1, 6, 7};
adjList* graph=new adjList(9, E, 14);
retList* A=MST_Kruskal(graph, weight, E);
A->print();
delete graph;
delete A;
return 0;
}